/*
 * @lc app=leetcode.cn id=140 lang=cpp
 *
 * [140] 单词拆分 II
 */

// @lc code=start
class Solution
{
public:
  vector<string> ans;

  vector<string> wordBreak(string s, vector<string>& wordDict)
  {
    ans = vector<string>();
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
          dp[i] = true;
          break;
        }
      }
    }
    if (dp[n]) {
      deque<string> dq;
      DFS(s, dict, dp, dq, n);
    }
    return ans;
  }

  void DFS(string& s, unordered_set<string>& dict, vector<bool>& dp, deque<string>& dq, int n)
  {
    if (n == 0) {
      string tmp;
      for (auto&& w : dq)
        tmp += w + " ";
      tmp.pop_back();
      ans.push_back(tmp);
    }
    else {
      for (int i = n - 1; i >= 0; --i) {
        string word = s.substr(i, n - i);
        if (dp[i] && dict.find(word) != dict.end()) {
          dq.push_front(word);
          DFS(s, dict, dp, dq, i);
          dq.pop_front();
        }
      }
    }
  }
};
// @lc code=end
